// https://leetcode.cn/problems/01-matrix/

// 题干：给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，
//      其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
//      两个相邻元素间的距离为 1 。

// 示例：输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//      输出：[[0,0,0],[0,1,0],[0,0,0]]

// 碎语：边权为1的多源BFS问题，解法是把多远最短路问题转化成若干个单源BFS最短路问题
//       另一种解法是把所有的源点当成一个超级源点，问题就变成了一个单一的单源最短路问题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int m, n;
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    typedef pair<int, int> PII;
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        // 把所有的起点加入到队列里面即可
        // 首先想到一个位置一个位置来求，会超时，最差情况下面会(n^3)

        // 正常解法是把所有的1当作一个超级源点，可是无法求出
        // 正难则反，把0当作起点，1当成终点

        // 遍历矩阵，把0的坐标坐下来
        m = mat.size(), n = mat[0].size();
        bool vis[m][n];
        memset(vis, 0, sizeof(vis));

        queue<PII> q;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++) {
                if (!mat[i][j]) {
                    q.push({i, j});
                    vis[i][j] = true;
                }
            }
        }

        int step = 0;
        while (q.size()){
            int sz = q.size();
            step++;

            while (sz--){
                auto [a, b] = q.front();
                q.pop();

                for (int k = 0 ; k < 4 ; k++){
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]){
                        mat[x][y] = step;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }

        return mat;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};

    vector<vector<int>> index = sol.updateMatrix(mat);
    for (const auto& arr : index){
        for (const auto& num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}